﻿// Vector datastructure.
//
// Copyright (C) 2012 M. de Wolde
//
// This program is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General
// Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option)
// any later version.
//
// This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied
// warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
// details.
//
// You should have received a copy of the GNU Lesser General Public License along with this program. If not, see
// <http://www.gnu.org/licenses/>.
//
// 2012-06-11 MIWO Created.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Text;
using System.Threading;

namespace Lemody.Glu {

/// <summary>Vector datastructure.</summary>
/// <remarks>
///     <para>
///         The vector supports array-like indexing. Indexes are 0-based. Inserting an element in the vector is
///         efficient and does not require to copy the elements after the insert position in order to make room for the
///         inserted element. Likewise deleting an element from the vector is efficient and does not require to copy the
///         elements after the delete position in order to fill the gap resulted from the delete. Accessing elements by
///         index is reasonably efficient, O(log n). This is less efficient than a true array or the generic List
///         datastructure, O(1), and more efficient than a linear search, O(n).
///     </para>
///     <para>
///         The vector can be used as an alternative to the generic List when performance of the list must be improved,
///         in cases where the list contains many elements, and many inserts and deletes are performed throughout the
///         list. Depending on the type of operations performed a list may be faster for up to 5.000 elements;
///         thereafter the vector is faster. From 50.000 elements and above the list performance deteriorates where the
///         vector performs as expected. When it comes to sorting the list is much faster; typically 20 times faster
///         regardless the number of elements. When it comes to binary searching the list is typically 3 times faster
///         than the vector.
///     </para>
/// </remarks>
[SerializableAttribute]
public class Vector<T>: IEnumerable<T>, ICollection<T>, IList<T>
{
    // The vector uses an Adelson-Velskii Landis tree. For an AVL tree any two subtrees differ in height by some
    // maximum. For this implementation the heights differ by one at most.

    // The Vector is written for int indexing and int counts. A distinct LongVector is written for long indexing and
    // long counts. Distinct copies of the source code are maintained for the Vector and LongVector. Tests with a
    // generic vector parameterized with int or long and a derived int Vector show a performance drop of a factor 5 to
    // 10, possibly because the language does not yet (C# 4.0) support to calculate with an int or long type specified
    // as a generic type parameter, having to fallback to conversion with boxing and unboxing or having to fallback to
    // typecheck deferring through the dynamic keyword. Maintaining distinct copies is facilitated: it is possible to
    // recreate the long version by copying the int version to the long version and by replacing int by long. The vector
    // code uses Int16 and Int32 when a short or int is intended regardless whether it is the Vector or LongVector. It
    // uses int and long for indexes, counts, offsets and other values that relate to the vector applying int or long
    // indexing.

    // Fields.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Root node, or null.</summary>
    private VectorNode<T> _rootNode;

    /// <summary>Update count, used to detect usage of the iterator after the vector has been modified.</summary>
    /// <remarks>The update count is incremented with each insert or delete, and wraps around at the end of the Int32 range.</remarks>
    private Int32 _updateCount;

    // Object management.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Default constructor, resulting in an empty vector.</summary>
    public Vector()
    {
        //
    }

    /// <summary>Constructor, resulting in a vector that contains elements copied from the specified collection.</summary>
    /// <remarks>The elements in the vector will be in the same order as in the collection.</remarks>
    /// <exception cref="ArgumentNullException">If the collection is null.</exception>
    /// <param name="collection">I: Collection.</param>
    public Vector(ICollection<T> collection)
    {
        CheckCollection(collection);
        foreach (T element in collection)
        {
            Add(element);
        }
    }

    /// <summary>Constructor, resulting in a vector that contains elements copied from the specified collection.</summary>
    /// <remarks>The elements in the vector will be in the same order as in the collection.</remarks>
    /// <exception cref="ArgumentNullException">If the collection is null.</exception>
    /// <param name="collection">I: Collection to copy.</param>
    public Vector(IEnumerable<T> collection)
    {
        CheckCollection(collection);
        foreach (T element in collection)
        {
            Add(element);
        }
    }

    /// <summary>Copy constructor.</summary>
    /// <remarks>The elements in the vector will be in the same order as in the original vector.</remarks>
    /// <exception cref="ArgumentNullException">If the supplied vector is null.</exception>
    /// <remarks>Results in a new vector containing the elements of the input vector.</remarks>
    public Vector(Vector<T> vector)
    {
        CheckVector(vector);
        VectorNode<T>.CopyAll(vector._rootNode, ref _rootNode);
    }

    /// <summary>Destructor.</summary>
    ~Vector()
    {
        if (_rootNode != null)
        {
            _rootNode.ClearSubtree();
        }
    }

    // Argument checking.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Checks that a vector index is greater than or equal to 0.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If the vector index is less than 0.</exception>
    /// <param name="index">I: Index.</param>
    private void CheckIndexGe0(int index)
    {
        if (index < 0)
        {
            Exception inner = null;
            throw new ArgumentOutOfRangeException("Vector index " + index.ToString() + " is out of range. A vector index " +
                "cannot be less than 0.", inner);
            //
        }
    }

    /// <summary>Checks that an array index is greater than or equal to 0.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If the array index is less than 0.</exception>
    /// <param name="index">I: Index.</param>
    private void CheckArrayIndexGe0(int index)
    {
        if (index < 0)
        {
            Exception inner = null;
            throw new ArgumentOutOfRangeException("Array index " + index.ToString() + " is out of range. An array index " +
                "cannot be less than 0.", inner);
            //
        }
    }

    /// <summary>Checks that an index is less than or equal to the vector element count.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If the index is greater than the vector element count.</exception>
    /// <param name="index">I: Index.</param>
    private void CheckIndexLeCount(int index)
    {
        if (index > Count)
        {
            Exception inner = null;
            throw new ArgumentOutOfRangeException("Vector index " + index.ToString() + " is out of range. The index cannot " +
                "exceed the vector element count " + Count.ToString() + ".", inner);
            //
        }
    }

    /// <summary>Checks that an index is less than the vector element count.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If the index is equal to or greater than the vector element count.</exception>
    /// <param name="index">I: Index.</param>
    private void CheckIndexLtCount(int index)
    {
        if (index >= Count)
        {
            Exception inner = null;
            throw new ArgumentOutOfRangeException("Vector index " + index.ToString() + " is out of range. The index cannot " +
                "be equal to or greater than the vector element count " + Count.ToString() + ".", inner);
            //
        }
    }

    /// <summary>Checks that a count is greater than or equal to 0.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If the count is less than 0.</exception>
    /// <param name="count">I: Count.</param>
    private void CheckCountGe0(int count)
    {
        if (count < 0)
        {
            Exception inner = null;
            throw new ArgumentOutOfRangeException("Count " + count.ToString() + " is out of range. A count that specifies " +
                "a vector range cannot be less than 0.", inner);
            //
        }
    }

    /// <summary>Checks that index + count is less than or equal to the vector element count.</summary>
    /// <exception cref="ArgumentException">If index + count exceeds the vector element count.</exception>
    /// <param name="index">I: Index.</param>
    /// <param name="count">I: Count.</param>
    private void CheckIndexPlusCountLeCount(int index, int count)
    {
        if (index + count > Count)
        {
            Exception inner = null;
            throw new ArgumentException("Index " + index.ToString() + " and count " + count.ToString() + " specify a range " +
                "that extends beyond the end of the vector which has an element count of " + Count.ToString() + ".", inner);
            //
        }
    }

    /// <summary>Checks that index + count is less than or equal to the array length.</summary>
    /// <exception cref="ArgumentException">If index + count exceeds the array length.</exception>
    /// <param name="index">I: Index.</param>
    /// <param name="count">I: Count.</param>
    /// <param name="length">I: Array length.</param>
    private void CheckArrayIndexPlusCountLeLength(int index, int count, int length)
    {
        if (index + count > length)
        {
            Exception inner = null;
            throw new ArgumentException("Index " + index.ToString() + " and count " + count.ToString() + " specify a range " +
                "that extends beyond the end of the array which is of length " + length.ToString() + ".", inner);
            //
        }
    }

    /// <summary>Checks that the count is less than or equal to the array length.</summary>
    /// <exception cref="ArgumentException">If the count exceeds the array length.</exception>
    /// <param name="count">I: Count.</param>
    /// <param name="length">I: Array length.</param>
    private void CheckCountLeArrayLength(int count, int length)
    {
        if (count > length)
        {
            Exception inner = null;
            throw new ArgumentException("Count " + count.ToString() + " exceeds the array which is of length " + length.ToString() + ".", inner);
        }
    }

    /// <summary>Checks that index - count is greater than or equal to 0.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If index - count is less than 0.</exception>
    /// <param name="index">I: Index.</param>
    /// <param name="count">I: Count.</param>
    private void CheckIndexMinCountGe0(int index, int count)
    {
        if (index - count < 0)
        {
            Exception inner = null;
            throw new ArgumentException("Index " + index.ToString() + " and reverse count " + count.ToString() + " specify a range " +
                "that extends to elements before the begin of the vector.", inner);
            //
        }
    }

    /// <summary>Checks that the start index is valid, where an index equal to the vector element count is accepted.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the index exceeds the vector element count.</exception>
    /// <param name="startIndex">I: Start index.</param>
    private void CheckStartIndex(int startIndex)
    {
        CheckIndexGe0(startIndex);
        CheckIndexLeCount(startIndex);
    }

    /// <summary>Checks that the at-index is valid, where an index equal to the vector element count is not accepted.</summary>
    /// <exception cref="ArgumentOutOfRangeException">
    ///     If the index is less than 0 or if the index is equal to or greater than the vector element count.
    /// </exception>
    /// <param name="atIndex">I: At index.</param>
    private void CheckAtIndex(int atIndex)
    {
        CheckIndexGe0(atIndex);
        CheckIndexLtCount(atIndex);
    }

    /// <summary>Checks a range specified by index and count.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the count is less than 0.</exception>
    /// <exception cref="ArgumentException">
    ///     If index + count exceeds the vector element count. A value equal to the vector element count is accepted.
    /// </exception>
    /// <param name="index">I: Index.</param>
    /// <param name="count">I: Count.</param>
    private void CheckRange(int index, int count)
    {
        CheckIndexGe0(index);
        CheckCountGe0(count);
        CheckIndexPlusCountLeCount(index, count);
    }

    /// <summary>Checks a range specified by index and count, where the count extends from the index towards the begin of the vector.</summary>
    /// <exception cref="ArgumentOutOfRangeException">
    ///     If the index is less than 0, the index exceeds the vector element count, the count is less than 0, or if index - count
    ///     is less than 0.
    /// </exception>
    /// <param name="index">I: Index.</param>
    /// <param name="count">I: Count.</param>
    private void CheckReverseRange(int index, int count)
    {
        CheckIndexGe0(index);
        CheckIndexLeCount(index);
        CheckCountGe0(count);
        CheckIndexMinCountGe0(index, count);
    }

    /// <summary>Checks the match predicate.</summary>
    /// <exception cref="ArgumentNullException">If the match predicate is null.</exception>
    /// <param name="match">I: Match predicate to check.</param>
    private static void CheckMatchPredicate(Predicate<T> match)
    {
        if (match == null)
        {
            Exception inner = null;
            throw new ArgumentNullException("The match predicate supplied to the vector must not be null.", inner);
        }
    }

    /// <summary>Checks the action delegate.</summary>
    /// <exception cref="ArgumentNullException">If the action delegate is null.</exception>
    /// <param name="action">I: Action delegate to check.</param>
    private static void CheckAction(Action<T> action)
    {
        if (action == null)
        {
            Exception inner = null;
            throw new ArgumentNullException("The action delegate supplied to the vector must not be null.", inner);
        }
    }

    /// <summary>Checks the supplied vector.</summary>
    /// <exception cref="ArgumentNullException">If the supplied vector is null.</exception>
    /// <param name="vector">I: Vector to check.</param>
    private static void CheckVector(Vector<T> vector)
    {
        if (vector == null)
        {
            Exception inner = null;
            throw new ArgumentNullException("The vector supplied to the current vector must not be null.", inner);
        }
    }

    /// <summary>Checks the collection.</summary>
    /// <exception cref="ArgumentNullException">If the collection is null.</exception>
    /// <param name="collection">I: Collection to check.</param>
    private static void CheckCollection(IEnumerable<T> collection)
    {
        if (collection == null)
        {
            Exception inner = null;
            throw new ArgumentNullException("The collection supplied to the vector must not be null.", inner);
        }
    }

    /// <summary>Checks the array.</summary>
    /// <exception cref="ArgumentNullException">If the array is null.</exception>
    /// <param name="array">I: Array to check.</param>
    private static void CheckArray(T[] array)
    {
        if (array == null)
        {
            Exception inner = null;
            throw new ArgumentNullException("The array supplied to the vector must not be null.", inner);
        }
    }

    /// <summary>Checks the comparer.</summary>
    /// <exception cref="InvalidOperationException">If the comparer is null and no default comparer can be established.</exception>
    /// <param name="comparer">I: Comparer to check.</param>
    private static void CheckComparer(IComparer<T> comparer)
    {
        if (comparer == null)
        {
            Exception inner = null;
            throw new InvalidOperationException("The comparer supplied to the vector is null, and no default comparer can be established.", inner);
        }
    }

    /// <summary>Checks the comparison.</summary>
    /// <exception cref="ArgumentNullException">If the comparison is null.</exception>
    /// <param name="comparison">I: Comparison to check.</param>
    private static void CheckComparison(Comparison<T> comparison)
    {
        if (comparison == null)
        {
            Exception inner = null;
            throw new InvalidOperationException("The comparison supplied to the vector is null.", inner);
        }
    }

    /// <summary>Checks the converter.</summary>
    /// <exception cref="ArgumentNullException">If the converter is null.</exception>
    /// <param name="converter">I: Converter to check.</param>
    private static void CheckConverter<TOutput>(Converter<T, TOutput> converter)
    {
        if (converter == null)
        {
            Exception inner = null;
            throw new ArgumentNullException("The converter supplied to the vector must not be null.", inner);
        }
    }

    // Implementation of the IEnumerable<T> and IEnumerable interface.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Returns an enumerator for the vector.</summary>
    public IEnumerator<T> GetEnumerator()
    {
        return new VectorEnumerator<T>(this);
    }

    /// <summary>Returns an enumerator for the vector.</summary>
    IEnumerator IEnumerable.GetEnumerator()
    {
        return new VectorEnumerator<T>(this);
    }

    // Implementation of the ICollection<T> interface.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Element count.</summary>
    public Int32 Count
    {
        [DebuggerStepThrough]
        get
        {
            return _rootNode == null? 0: _rootNode.Count;
        }
    }

    /// <summary>Whether the vector is read-only.</summary>
    /// <remarks>A vector is read-write by default. A read-only wrapper vector obtained from the vector is read-only.</remarks>
    public bool IsReadOnly
    {
        [DebuggerStepThrough]
        get
        {
            return false;
        }
    }

    /// <summary>Adds an element at the end of the vector.</summary>
    /// <param name="element">I: Element to insert.</param>
    public void Add(T element)
    {
        Insert(_rootNode == null? 0: _rootNode.Count, element);
    }

    /// <summary>Clears the vector.</summary>
    /// <remarks>The method removes all elements from the vector.</remarks>
    public void Clear()
    {
        if (_rootNode != null)
        {
            _rootNode.ClearSubtree();
            _rootNode = null;
            _updateCount++;
        }
    }

    /// <summary>Determines whether the vector contains a specific element.</summary>
    /// <remarks>The method uses the default equality comparer for T to perform a linear search.</remarks>
    /// <param name="element">I: Element to look for. This can be null for reference types.</param>
    public bool Contains(T element)
    {
        var comparer = EqualityComparer<T>.Default;
        bool contains = false;
        foreach (T candidate in this)
        {
            if (comparer.Equals(candidate, element))
            {
                contains = true;
                break;
            }
        }
        return contains;
    }

    /// <summary>Copies the elements of the vector to an array, starting at a particular array index.</summary>
    /// <remarks>
    ///     The method does not resize the destination array; the array must already include the element slots for the
    ///     copied elements.
    /// </remarks>
    /// <exception cref="ArgumentNullException">If the array is null.</exception>
    /// <exception cref="ArgumentOutOfRangeException">If the array index is less than 0.</exception>
    /// <exception cref="ArgumentException">If the destination range extends beyond the end of the array.</exception>
    /// <param name="array">IO: Destination array.</param>
    /// <param name="index">I: Array index, 0-based.</param>
    public void CopyTo(T[] array, Int32 index)
    {
        CheckArray(array);
        CheckArrayIndexGe0(index);
        CheckArrayIndexPlusCountLeLength(index, Count, array.Length);
        foreach (T element in this)
        {
            array[index] = element;
            index++;
        }
    }

    /// <summary>Removes the first occurrence of a specific element from the vector.</summary>
    /// <remarks>The method performs a linear search.</remarks>
    /// <param name="element">I: Element to look for. The method determines equality using the default equality comparer for T.</param>
    /// <returns>True if an element was removed.</returns>
    public bool Remove(T element)
    {
        var comparer = EqualityComparer<T>.Default;
        int index = 0;
        bool removed = false;
        foreach (T candidate in this)
        {
            if (comparer.Equals(candidate, element))
            {
                RemoveAt(index);
                removed = true;
                break;
            }
            index++;
        }
        return removed;
    }

    // Implementation of the IList<T> interface.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Returns the element at the specified index.</summary>
    /// <remarks>
    ///     Accessing an element by index is efficient, although not as efficient as for a true array. If the element is
    ///     accessed more than once and the element is a reference type consider storing the reference, using the
    ///     reference to read and update the element. If the element is a value type consider obtaining a vector node,
    ///     which is a reference type, storing the reference to the node and using that reference to read and update the
    ///     element in the node.
    /// </remarks>
    /// <exception cref="ArgumentOutOfRangeException">
    ///     If the index is less than 0 or if the index is equal to or greater than the vector element count.
    /// </exception>
    /// <param name="index">I: Index, 0-based, must be valid.</param>
    public T this[Int32 index]
    {
        set
        {
            CheckAtIndex(index);
            _rootNode.GetNode(index, 0).Element = value;
        }
        get
        {
            CheckAtIndex(index);
            return _rootNode.GetNode(index, 0).Element;
        }
    }

    /// <summary>Determines the index of a specific element in the vector.</summary>
    /// <remarks>
    ///     The method returns the index of the first element if the element occurs multiple times. The method performs
    ///     a linear search. The method uses the default equality comparer for the type.
    /// </remarks>
    /// <param name="element">I: Element to look for. This can be null for reference types.</param>
    /// <returns>Index, 0-based, or -1 if not found.</returns>
    public Int32 IndexOf(T element)
    {
        var comparer = EqualityComparer<T>.Default;
        int index = 0;
        bool found = false;
        foreach (T candidate in this)
        {
            if (comparer.Equals(candidate, element))
            {
                found = true;
                break;
            }
            index++;
        }
        return found? Convert.ToInt32(index): -1;
    }

    /// <summary>Inserts an element in the vector at the specified index.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the index exceeds the vector element count.</exception>
    /// <param name="index">I: Index, zero based. Use the vector element count to insert at the end.</param>
    /// <param name="element">I: element to insert.</param>
    public void Insert(Int32 index, T element)
    {
        CheckStartIndex(index);
        Int32 heightChange;
        VectorNode<T>.Insert(index, 0, element, null, ref _rootNode, out heightChange);
        _updateCount++;
    }

    /// <summary>Removes an element from the vector.</summary>
    /// <exception cref="ArgumentOutOfRangeException">
    ///     If the index is less than 0 or if the index is equal to or greater than the vector element count.
    /// </exception>
    /// <param name="index">I: Index of the element to remove, 0-based.</param>
    public void RemoveAt(Int32 index)
    {
        CheckAtIndex(index);
        Debug.Assert(_rootNode != null);
        Int32 heightChange;
        VectorNode<T>.Delete(index, 0, null, ref _rootNode, out heightChange);
        _updateCount++;
    }

    // Implementations for compatibility with class List<T>.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Adds the elements of the specified collection to the end of the vector.</summary>
    /// <exception cref="ArgumentNullException">If the collection is null.</exception>
    /// <param name="collection">I: Collection, not null.</param>
    public void AddRange(IEnumerable<T> collection)
    {
        CheckCollection(collection);
        foreach (T element in collection)
        {
            Add(element);
        }
    }

    /// <summary>Returns a read-only wrapper for the current vector.</summary>
    /// <returns></returns>
    public ReadOnlyCollection<T> AsReadOnly()
    {
        var asReadOnly = new ReadOnlyCollection<T>(this);
        return asReadOnly;
    }

    /// <summary>Returns the default comparer given the generic type.</summary>
    /// <remarks>
    ///     This is the default comparer for all types except string. The string default comparer depends on the current
    ///     culture. This is for compatibility with the List generic collection.
    /// </remarks>
    /// <exception cref="InvalidOperationException">If no default comparer can be established.</exception>
    private static IComparer<T> DefaultComparer
    {
        [DebuggerStepThrough]
        get
        {
            IComparer<T> comparer = typeof(T) == typeof(string)? (IComparer<T>) StringComparer.CurrentCulture: Comparer<T>.Default;
            CheckComparer(comparer);
            return comparer;
        }
    }

    /// <summary>Searches the vector for the element and returns the index of the found element.</summary>
    /// <remarks>
    ///     The method performs a binary search using the default comparer for the generic type. If the generic type is
    ///     a string the comparer is the string comparer for the current culture.
    /// </remarks>
    /// <exception cref="InvalidOperationException">If no default comparer can be established.</exception>
    /// <param name="element">I: Element to look for.</param>
    /// <returns>
    ///     Index, 0-based, or a negative number of the element is not found. The negative number is the bitwise
    ///     complement of the index of the next element that is larger than element or, if there is no larger element, the
    ///     bitwise complement of Count.
    /// </returns>
    public int BinarySearch(T element)
    {
        return BinarySearch(element, DefaultComparer);
    }

    /// <summary>Searches the vector for the element and returns the index of the found element.</summary>
    /// <remarks>The method performs a binary search.</remarks>
    /// <exception cref="InvalidOperationException">If the comparer is null and no default comparer can be established.</exception>
    /// <param name="element">I: Element to look for.</param>
    /// <param name="comparer">I: Comparer, or null to use the default comparer for the type.</param>
    /// <returns>
    ///     Index, 0-based, or a negative number of the element is not found. The negative number is the bitwise
    ///     complement of the index of the next element that is larger than element or, if there is no larger element, the
    ///     bitwise complement of Count.
    /// </returns>
    public int BinarySearch(T element, IComparer<T> comparer)
    {
        if (comparer == null)
        {
            comparer = DefaultComparer;
        }
        return _rootNode == null? ~0: Convert.ToInt32(_rootNode.BinarySearch(element, comparer, 0));
    }

    /// <summary>Searches the vector for the element and returns the index of the found element.</summary>
    /// <remarks>The method performs a binary search. The method searches the specified range only.</remarks>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the count is less than 0.</exception>
    /// <exception cref="ArgumentException">
    ///     If index + count exceeds the vector element count. A value equal to the vector element count is accepted.
    /// </exception>
    /// <exception cref="InvalidOperationException">If the comparer is null and no default comparer can be established.</exception>
    /// <param name="index">I: Starting index of the range to search, 0-based.</param>
    /// <param name="count">I: Length of the range to search.</param>
    /// <param name="element">I: Element to look for.</param>
    /// <param name="comparer">I: Comparer, or null to use the default comparer for the type.</param>
    /// <returns>
    ///     Index, 0-based, or a negative number of the element is not found. The negative number is the bitwise
    ///     complement of the index of the next element that is larger than element or, if there is no larger element, the
    ///     bitwise complement of Count.
    /// </returns>
    public int BinarySearch(int index, int count, T element, IComparer<T> comparer)
    {
        CheckRange(index, count);
        if (comparer == null)
        {
            comparer = DefaultComparer;
        }
        return _rootNode == null? ~0: Convert.ToInt32(_rootNode.BinarySearch(index, count, element, comparer, 0));
    }

    /// <summary>Converts the elements in the current vector to another type, and returns a vector containing the converted elements.</summary>
    /// <exception cref="ArgumentNullException">If the converter is null.</exception>
    /// <typeparam name="TOutput">I: The type of the elements in the target vector.</typeparam>
    /// <param name="converter">I: Delegate that performs the element conversion.</param>
    public Vector<TOutput> ConvertAll<TOutput>(Converter<T, TOutput> converter)
    {
        CheckConverter(converter);
        var vector = new Vector<TOutput>();
        VectorNode<T>.ConvertAll(_rootNode, converter, ref vector._rootNode);
        return vector;
    }

    /// <summary>Copies the entire vector to a compatible one-dimensional array, starting at the beginning of the target array.</summary>
    /// <exception cref="ArgumentNullException">If the array is null.</exception>
    /// <exception cref="ArgumentException">If the count exceeds the array length.</exception>
    /// <param name="array">IO: Array that is the destination of copied elements.</param>
    public void CopyTo(T[] array)
    {
        CheckArray(array);
        CheckCountLeArrayLength(Count, array.Length);
        int i = 0;
        foreach (T element in this)
        {
            array[i] = element;
            i++;
        }
    }

    /// <summary>
    ///     Copies a range of elements from the vector to a compatible one-dimensional array, starting at the specified
    ///     index of the target array.
    /// </summary>
    /// <exception cref="ArgumentNullException">If the array is null.</exception>
    /// <exception cref="ArgumentOutOfRangeException">
    ///     If the vector index is less than 0, or the array index is less than 0, or the count is less than 0.
    /// </exception>
    /// <exception cref="ArgumentException">If index + count exceeds the vector length, or arrayIndex + count exceeds the array length.</exception>
    /// <param name="index">I: Start index in the vector, 0-based.</param>
    /// <param name="array">IO: Array that is the destination of copied elements.</param>
    /// <param name="arrayIndex">I: Start index in the array, 0-based.</param>
    /// <param name="count">I: Number of elements to copy.</param>
    public void CopyTo(int index, T[] array, int arrayIndex, int count)
    {
        CheckArray(array);
        CheckIndexGe0(index);
        CheckArrayIndexGe0(arrayIndex);
        CheckCountGe0(count);
        CheckIndexPlusCountLeCount(index, count);
        CheckArrayIndexPlusCountLeLength(arrayIndex, count, array.Length);
        for (int i = 0; i != count; i++)
        {
            array[arrayIndex + i] = this[index + i];
        }
    }

    /// <summary>Whether the specified vector is equal to the current vector.</summary>
    /// <param name="obj">I: Vector to test.</param>
    public override bool Equals(object obj)
    {
        bool equal = false;
        if (!ReferenceEquals(obj, null) && obj is Vector<T>)
        {
            var vector = (Vector<T>) obj;
            if (Count == vector.Count)
            {
                equal = true;
                VectorEnumerator<T> e1 = this.GetVectorEnumerator();
                VectorEnumerator<T> e2 = vector.GetVectorEnumerator();
                while (equal && e1.MoveNext())
                {
                    e2.MoveNext();
                    equal = e1.Current.Equals(e2.Current);
                }
            }
        }
        return equal;
    }

    /// <summary>Determines whether the vector contains elements that match the conditions defined by the predicate.</summary>
    /// <remarks>The method performs a linear search.</remarks>
    /// <exception cref="ArgumentNullException">If the match predicate is null.</exception>
    /// <param name="match">I: The delegate that defines the conditions of the elements to search for.</param>
    /// <returns>True if at least one element is found, false otherwise.</returns>
    public bool Exists(Predicate<T> match)
    {
        CheckMatchPredicate(match);
        bool exists = false;
        foreach (T element in this)
        {
            if (match(element))
            {
                exists = true;
                break;
            }
        }
        return exists;
    }

    /// <summary>
    ///     Searches for an element that matches the conditions defined by the predicate, and returns the first occurrence
    ///     within the entire vector.
    /// </summary>
    /// <remarks>The method performs a linear search.</remarks>
    /// <exception cref="ArgumentNullException">If the match predicate is null.</exception>
    /// <param name="match">I: The delegate that defines the conditions of the elements to search for.</param>
    /// <returns>Returns the first occurrence of the found element, or returns the default value for the type if not found.</returns>
    public T Find(Predicate<T> match)
    {
        CheckMatchPredicate(match);
        T foundValue = default(T);
        foreach (T element in this)
        {
            if (match(element))
            {
                foundValue = element;
                break;
            }
        }
        return foundValue;
    }

    /// <summary>Retrieves all the element that match the conditions defined by the predicate.</summary>
    /// <remarks>The method performs a linear search.</remarks>
    /// <exception cref="ArgumentNullException">If the match predicate is null.</exception>
    /// <param name="match">I: The delegate that defines the conditions of the elements to search for.</param>
    /// <returns>A vector containing all the matching elements, or an empty vector if not found.</returns>
    public Vector<T> FindAll(Predicate<T> match)
    {
        CheckMatchPredicate(match);
        var vector = new Vector<T>();
        foreach (T element in this)
        {
            if (match(element))
            {
                vector.Add(element);
            }
        }
        return vector;
    }

    /// <summary>
    ///     Searches for an element that matches the conditions defined by the predicate, and returns the 0-based index
    ///     of the first occurrence within the entire vector.
    /// </summary>
    /// <remarks>The method performs a linear search.</remarks>
    /// <exception cref="ArgumentNullException">If the match predicate is null.</exception>
    /// <param name="match">I: The delegate that defines the conditions of the elements to search for.</param>
    /// <returns>The 0-based index of the first occurrence of the element; or –1 if not found.</returns>
    public int FindIndex(Predicate<T> match)
    {
        CheckMatchPredicate(match);
        bool found = false;
        int index = 0;
        foreach (T element in this)
        {
            if (match(element))
            {
                found = true;
                break;
            }
            index++;
        }
        return found? index: -1;
    }

    /// <summary>
    ///     Searches for an element that matches the conditions defined by the predicate, and returns the 0-based index
    ///     of the first occurrence within the range of elements in the vector that extends from the specified index to
    ///     the last element.
    /// </summary>
    /// <remarks>The method performs a linear search.</remarks>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the index exceeds the vector element count.</exception>
    /// <exception cref="ArgumentNullException">If the match predicate is null.</exception>
    /// <param name="startIndex">
    ///     I: 0-based index of the first element in the range. An index equal to the vector element count is accepted
    ///     and results in not found.
    /// </param>
    /// <param name="match">I: The delegate that defines the conditions of the elements to search for.</param>
    /// <returns>The 0-based index of the first occurrence of the element; or –1 if not found.</returns>
    public int FindIndex(int startIndex, Predicate<T> match)
    {
        CheckStartIndex(startIndex);
        CheckMatchPredicate(match);
        VectorEnumerator<T> e = GetVectorEnumerator(startIndex);
        bool found = false;
        int index = startIndex;
        while (!found && e.MoveNext())
        {
            if (match(e.Current))
            {
                found = true;
            }
            else
            {
                index++;
            }
        }
        return found? index: -1;
    }

    /// <summary>
    ///     Searches for an element that matches the conditions defined by the predicate, and returns the 0-based index
    ///     of the first occurrence within the range of elements in the vector that extends from the element at the
    ///     specified index and for the specified number of elements.
    /// </summary>
    /// <remarks>The method performs a linear search.</remarks>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the count is less than 0.</exception>
    /// <exception cref="ArgumentException">
    ///     If index + count exceeds the vector element count. A value equal to the vector element count is accepted.
    /// </exception>
    /// <exception cref="ArgumentNullException">If the match predicate is null.</exception>
    /// <param name="startIndex">
    ///     I: 0-based index of the first element in the range. An index equal to the vector element count is acceptable
    ///     provided that the count argument is 0.
    /// </param>
    /// <param name="count">I: Number of elements to search, 0 or more.</param>
    /// <param name="match">I: The delegate that defines the conditions of the elements to search for.</param>
    /// <returns>The 0-based index of the first occurrence of the element; or –1 if not found.</returns>
    public int FindIndex(int startIndex, int count, Predicate<T> match)
    {
        CheckRange(startIndex, count);
        CheckMatchPredicate(match);
        VectorEnumerator<T> e = GetVectorEnumerator(startIndex);
        bool found = false;
        int index = startIndex;
        while (!found && count != 0 && e.MoveNext())
        {
            if (match(e.Current))
            {
                found = true;
            }
            else
            {
                count--;
                index++;
            }
        }
        return found? index: -1;
    }

    /// <summary>
    ///     Searches for an element that matches the conditions defined by the predicate, and returns the last occurrence
    ///     within the entire vector.
    /// </summary>
    /// <remarks>The method performs a linear search.</remarks>
    /// <exception cref="ArgumentNullException">If the match predicate is null.</exception>
    /// <param name="match">I: The delegate that defines the conditions of the elements to search for.</param>
    /// <returns>Returns the last occurrence of the found element, or returns the default value for the type if not found.</returns>
    public T FindLast(Predicate<T> match)
    {
        CheckMatchPredicate(match);
        T foundValue = default(T);
        VectorEnumerator<T> e = GetVectorEnumerator(Count);
        while (e.MovePrevious())
        {
            if (match(e.Current))
            {
                foundValue = e.Current;
                break;
            }
        }
        return foundValue;
    }

    /// <summary>
    ///     Searches for an element that matches the conditions defined by the predicate, and returns the 0-based index
    ///     of the last occurrence within the entire vector.
    /// </summary>
    /// <remarks>The method performs a linear search.</remarks>
    /// <exception cref="ArgumentNullException">If the match predicate is null.</exception>
    /// <param name="match">I: The delegate that defines the conditions of the elements to search for.</param>
    /// <returns>The 0-based index of the last occurrence of the element; or –1 if not found.</returns>
    public int FindLastIndex(Predicate<T> match)
    {
        CheckMatchPredicate(match);
        bool found = false;
        int index = Count;
        VectorEnumerator<T> e = GetVectorEnumerator(Count);
        while (!found && e.MovePrevious())
        {
            index--;
            if (match(e.Current))
            {
                found = true;
            }
        }
        return found? index: -1;
    }

    /// <summary>
    ///     Searches for an element that matches the conditions defined by the predicate, and returns the 0-based index
    ///     of the last occurrence within the range of elements in the vector that extends from the the element at the
    ///     specified index to the first element.
    /// </summary>
    /// <remarks>The method performs a linear search.</remarks>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the index exceeds the vector element count.</exception>
    /// <exception cref="ArgumentNullException">If the match predicate is null.</exception>
    /// <param name="startIndex">I: 0-based index of the start element in the range. The index can be equal to the vector element count.</param>
    /// <param name="match">I: The delegate that defines the conditions of the elements to search for.</param>
    /// <returns>The 0-based index of the last occurrence of the element; or –1 if not found.</returns>
    public int FindLastIndex(int startIndex, Predicate<T> match)
    {
        CheckStartIndex(startIndex);
        CheckMatchPredicate(match);
        VectorEnumerator<T> e = GetVectorEnumerator(startIndex);
        bool found = false;
        int index = startIndex == Count? startIndex - 1: startIndex;
        while (!found && e.MovePrevious())
        {
            if (match(e.Current))
            {
                found = true;
            }
            else
            {
                index--;
            }
        }
        return found? index: -1;
    }

    /// <summary>
    ///     Searches for an element that matches the conditions defined by the predicate, and returns the 0-based index
    ///     of the last occurrence within the range of elements in the vector that extends from the element at the
    ///     specified index and for the specified number of elements in backward direction.
    /// </summary>
    /// <remarks>The method performs a linear search.</remarks>
    /// <exception cref="ArgumentOutOfRangeException">
    ///     If the index is less than 0, the index exceeds the vector element count, the count is less than 0, or if index - count
    ///     is less than 0.
    /// </exception>
    /// <exception cref="ArgumentNullException">If the match predicate is null.</exception>
    /// <param name="startIndex">I: 0-based index of the start element in the range. The index can be equal to the vector element count.</param>
    /// <param name="count">I: Number of elements to search in backward direction, 0 or more.</param>
    /// <param name="match">I: The delegate that defines the conditions of the elements to search for.</param>
    /// <returns>The 0-based index of the last occurrence of the element; or –1 if not found.</returns>
    public int FindLastIndex(int startIndex, int count, Predicate<T> match)
    {
        CheckReverseRange(startIndex, count);
        CheckMatchPredicate(match);
        VectorEnumerator<T> e = GetVectorEnumerator(startIndex);
        bool found = false;
        int index = startIndex == Count? startIndex - 1: startIndex;
        while (!found && count != 0 && e.MovePrevious())
        {
            if (match(e.Current))
            {
                found = true;
            }
            else
            {
                count--;
                index--;
            }
        }
        return found? index: -1;
    }

    /// <summary>Performs the specified action on each element in the vector.</summary>
    /// <exception cref="ArgumentNullException">If the action delegate is null.</exception>
    /// <param name="action">I: Action to perform.</param>
    public void ForEach(Action<T> action)
    {
        CheckAction(action);
        foreach (T element in this)
        {
            action(element);
        }
    }

    /// <summary>Returns a hash code of the vector.</summary>
    /// <remarks>The method visits all elements in order to establish the hash.</remarks>
    public override Int32 GetHashCode()
    {
        Int32 hash = Count.GetHashCode();
        foreach (T element in this)
        {
            hash ^= element.GetHashCode();
        }
        return hash;
    }

    /// <summary>Creates a shallow copy of a range of elements in the source vector.</summary>
    /// <remarks>
    ///     For a vector of a value type the elements are copied by value. For a vector of a reference type the
    ///     references are copied without copying the referred object.
    /// </remarks>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the count is less than 0.</exception>
    /// <exception cref="ArgumentException">
    ///     If index + count exceeds the vector element count. A value equal to the vector element count is accepted.
    /// </exception>
    /// <param name="index">I: Start index, 0-based.</param>
    /// <param name="count">I: Number of elements to copy.</param>
    /// <returns></returns>
    public Vector<T> GetRange(int index, int count)
    {
        CheckRange(index, count);
        Vector<T> result;
        if (index == 0 && count == Count)
        {
            result = new Vector<T>(this);
        }
        else
        {
            result = new Vector<T>();
            VectorEnumerator<T> e = GetVectorEnumerator(index);
            while (count != 0)
            {
                Trace.Assert(e.MoveNext());
                result.Add(e.Current);
                count--;
            }
        }
        return result;
    }

    /// <summary>
    ///     Searches for the specified element and returns the 0-based index of the first occurrence within the range of
    ///     elements in the vector that extends from the specified index to the last element.
    /// </summary>
    /// <remarks>The method uses the default equality comparer for the type. The method performs a linear search.</remarks>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the index exceeds the vector element count.</exception>
    /// <param name="element">I: Element to look for.</param>
    /// <param name="startIndex">
    ///     I: 0-based index of the first element in the range. An index equal to the vector element count is acceptable and
    ///     always results in not found.
    /// </param>
    /// <returns>The 0-based index of the first occurrence of the element; or –1 if not found.</returns>
    public int IndexOf(T element, int startIndex)
    {
        CheckStartIndex(startIndex);
        VectorEnumerator<T> e = GetVectorEnumerator(startIndex);
        bool found = false;
        int index = startIndex;
        var comparer = EqualityComparer<T>.Default;
        while (!found && e.MoveNext())
        {
            if (comparer.Equals(e.Current, element))
            {
                found = true;
            }
            else
            {
                index++;
            }
        }
        return found? index: -1;
    }

    /// <summary>
    ///     Searches for the specified element and returns the 0-based index of the first occurrence within the range of
    ///     elements in the vector that starts at the specified index and contains the specified number of elements.
    /// </summary>
    /// <remarks>The method uses the default equality comparer for the type. The method performs a linear search.</remarks>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the count is less than 0.</exception>
    /// <exception cref="ArgumentException">
    ///     If index + count exceeds the vector element count. A value equal to the vector element count is accepted.
    /// </exception>
    /// <param name="element">I: Element to look for.</param>
    /// <param name="startIndex">
    ///     I: 0-based index of the first element in the range. An index equal to the vector element count is acceptable
    ///     provided that the count argument is 0.
    /// </param>
    /// <param name="count">I: Number of elements to search, 0 or more.</param>
    /// <returns>The 0-based index of the first occurrence of the element; or –1 if not found.</returns>
    public int IndexOf(T element, int startIndex, int count)
    {
        CheckRange(startIndex, count);
        VectorEnumerator<T> e = GetVectorEnumerator(startIndex);
        bool found = false;
        int index = startIndex;
        var comparer = EqualityComparer<T>.Default;
        while (!found && count != 0 && e.MoveNext())
        {
            if (comparer.Equals(e.Current, element))
            {
                found = true;
            }
            else
            {
                count--;
                index++;
            }
        }
        return found? index: -1;
    }

    /// <summary>Inserts the elements of a collection into the vector at the specified index.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the index exceeds the vector element count.</exception>
    /// <exception cref="ArgumentNullException">If the collection is null.</exception>
    /// <param name="index">I: Index in the vector where to start inserting.</param>
    /// <param name="collection">I: Collection to insert.</param>
    public void InsertRange(int index, IEnumerable<T> collection)
    {
        CheckStartIndex(index);
        CheckCollection(collection);
        foreach (T element in collection)
        {
            Insert(index, element);
            index++;
        }
    }

    /// <summary>Searches for the specified element and returns the 0-based index of the last occurrence within the entire vector.</summary>
    /// <remarks>The method uses the default equality comparer for the type. The method performs a linear search.</remarks>
    /// <param name="element">I: Element to look for.</param>
    /// <returns>The 0-based index of the last occurrence of the element; or –1 if not found.</returns>
    public int LastIndexOf(T element)
    {
        bool found = false;
        int index = Count;
        VectorEnumerator<T> e = GetVectorEnumerator(Count);
        var comparer = EqualityComparer<T>.Default;
        while (!found && e.MovePrevious())
        {
            index--;
            if (comparer.Equals(e.Current, element))
            {
                found = true;
            }
        }
        return found? index: -1;
    }

    /// <summary>
    ///     Searches for the element and returns the 0-based index of the last occurrence within the range of elements
    ///     in the vector that extends from the element at the specified index to the first element of the vector.
    /// </summary>
    /// <remarks>The method uses the default equality comparer for the type. The method performs a linear search.</remarks>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the index exceeds the vector element count.</exception>
    /// <param name="element">I: Element to look for.</param>
    /// <param name="index">
    ///     I: 0-based index of the element where to start the backward search. The index can be equal to the vector
    ///     element count.
    /// </param>
    /// <returns>The 0-based index of the last occurrence of the element; or –1 if not found.</returns>
    public int LastIndexOf(T element, int index)
    {
        CheckStartIndex(index);
        VectorEnumerator<T> e = GetVectorEnumerator(index);
        bool found = false;
        if (index == Count)
        {
            index--;
        }
        var comparer = EqualityComparer<T>.Default;
        while (!found && e.MovePrevious())
        {
            if (comparer.Equals(e.Current, element))
            {
                found = true;
            }
            else
            {
                index--;
            }
        }
        return found? index: -1;
    }

    /// <summary>
    ///     Searches for the element and returns the 0-based index of the last occurrence within the range of elements
    ///     in the vector that extends from the element at the specified index and for the specified number of elements
    ///     in backward direction.
    /// </summary>
    /// <remarks>The method uses the default equality comparer for the type. The method performs a linear search.</remarks>
    /// <exception cref="ArgumentOutOfRangeException">
    ///     If the index is less than 0, the index exceeds the vector element count, the count is less than 0, or if index - count
    ///     is less than 0.
    /// </exception>
    /// <param name="element">I: Element to look for.</param>
    /// <param name="index">I: 0-based index of the start element in the range. The index can be equal to the vector element count.</param>
    /// <param name="count">I: Number of elements to search in backward direction, 0 or more.</param>
    /// <returns>The 0-based index of the last occurrence of the element; or –1 if not found.</returns>
    public int LastIndexOf(T element, int index, int count)
    {
        CheckReverseRange(index, count);
        VectorEnumerator<T> e = GetVectorEnumerator(index);
        bool found = false;
        if (index == Count)
        {
            index--;
        }
        var comparer = EqualityComparer<T>.Default;
        while (!found && count != 0 && e.MovePrevious())
        {
            if (comparer.Equals(e.Current, element))
            {
                found = true;
            }
            else
            {
                count--;
                index--;
            }
        }
        return found? index: -1;
    }

    /// <summary>Removes all the elements that match the conditions defined by the specified predicate.</summary>
    /// <remarks>The method performs a linear search in order to remove.</remarks>
    /// <exception cref="ArgumentNullException">If the match predicate is null.</exception>
    /// <param name="match">I: The predicate delegate that defines the conditions of the elements to remove.</param>
    /// <returns>The number of elements removed from the vector.</returns>
    public int RemoveAll(Predicate<T> match)
    {
        CheckMatchPredicate(match);
        var indexes = new Vector<int>();
        int index = 0;
        foreach (T element in this)
        {
            if (match(element))
            {
                indexes.Add(index);
            }
            index++;
        }
        VectorEnumerator<int> e = indexes.GetVectorEnumerator(indexes.Count);
        while (e.MovePrevious())
        {
            RemoveAt(e.Current);
        }
        return indexes.Count;
    }

    /// <summary>Removes a range of elements from the vector.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the count is less than 0.</exception>
    /// <exception cref="ArgumentException">
    ///     If index + count exceeds the vector element count. A value equal to the vector element count is accepted.
    /// </exception>
    /// <param name="index">I: The 0-based start index of the range of elements to remove.</param>
    /// <param name="count">I: The number of elements to remove.</param>
    public void RemoveRange(int index, int count)
    {
        CheckRange(index, count);
        while (count != 0)
        {
            count--;
            RemoveAt(index + count);
        }
    }

    /// <summary>Reverses the order of the elements in the entire vector.</summary>
    /// <remarks>This method requires to visit all elements.</remarks>
    public void Reverse()
    {
        int count = Count;
        VectorEnumerator<T> e1 = GetVectorEnumerator();
        VectorEnumerator<T> e2 = GetVectorEnumerator(count);
        count /= 2;
        while (count != 0 && e1.MoveNext() && e2.MovePrevious())
        {
            T element = e1.Current;
            e1.Current = e2.Current;
            e2.Current = element;
            count--;
        }
        Debug.Assert(count == 0);
    }

    /// <summary>Reverses the order of the elements in the specified range.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the count is less than 0.</exception>
    /// <exception cref="ArgumentException">
    ///     If index + count exceeds the vector element count. A value equal to the vector element count is accepted.
    /// </exception>
    /// <param name="index">I: The 0-based starting index of the range to reverse.</param>
    /// <param name="count">I: The number of elements in the range to reverse.</param>
    public void Reverse(int index, int count)
    {
        CheckRange(index, count);
        VectorEnumerator<T> e1 = GetVectorEnumerator(index);
        VectorEnumerator<T> e2 = GetVectorEnumerator(index + count - 1);
        count /= 2;
        while (count != 0 && e1.MoveNext() && e2.MovePrevious())
        {
            T element = e1.Current;
            e1.Current = e2.Current;
            e2.Current = element;
            count--;
        }
        Debug.Assert(count == 0);
    }

    /// <summary>Sorts the vector using the default comparer for the generic type.</summary>
    /// <remarks>If the generic type is a string the comparer is the string comparer for the current culture.</remarks>
    /// <exception cref="InvalidOperationException">If no default comparer can be established.</exception>
    public void Sort()
    {
        // Sort by rebuilding the vector using binary searches for sorted inserts. Process the leaf nodes first, working
        // towards the root. Free the nodes as soon as processed, avoiding that memory usage doubles during the sort.
        Int32 targetLevel = GetHeight();
        VectorNode<T> rootNode = _rootNode;
        _rootNode = null;
        while (targetLevel != 0)
        {
            VectorNode<T>.Sort(DefaultComparer, 0, targetLevel, ref rootNode, this);
            targetLevel--;
        }
        Debug.Assert(rootNode == null);
    }

    /// <summary>Sorts the vector using the specified comparer.</summary>
    /// <exception cref="ArgumentNullException">If the comparison is null.</exception>
    /// <param name="comparison">I: The comparer to use.</param>
    public void Sort(Comparison<T> comparison)
    {
        CheckComparison(comparison);
        Sort(new VectorComparisonComparer<T>(comparison));
    }

    /// <summary>Sorts the vector using the specified comparer.</summary>
    /// <exception cref="InvalidOperationException">If the comparer is null and no default comparer can be established.</exception>
    /// <param name="comparer">I: The comparer to use, or null for the default comparer.</param>
    public void Sort(IComparer<T> comparer)
    {
        if (comparer == null)
        {
            comparer = DefaultComparer;
        }
        // Sort by rebuilding the vector using binary searches for sorted inserts. Process the leaf nodes first, working
        // towards the root. Free the nodes as soon as processed, avoiding that memory usage doubles during the sort.
        Int32 targetLevel = GetHeight();
        VectorNode<T> rootNode = _rootNode;
        _rootNode = null;
        while (targetLevel != 0)
        {
            VectorNode<T>.Sort(comparer, 0, targetLevel, ref rootNode, this);
            targetLevel--;
        }
        Debug.Assert(rootNode == null);
    }
    
    /// <summary>Sorts a range of elements in the vector, using the specified comparer.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the count is less than 0.</exception>
    /// <exception cref="ArgumentException">
    ///     If index + count exceeds the vector element count. A value equal to the vector element count is accepted.
    /// </exception>
    /// <exception cref="InvalidOperationException">If the comparer is null and no default comparer can be established.</exception>
    /// <param name="index">I: The 0-based start index of the range to sort.</param>
    /// <param name="count">I: The length of the range to sort.</param>
    /// <param name="comparer">I: The comparer to use, or null for the default comparer.</param>
    public void Sort(int index, int count, IComparer<T> comparer)
    {
        if (index == 0 && count == Count)
        {
            Sort(comparer);
        }
        else
        {
            CheckRange(index, count);
            if (comparer == null)
            {
                comparer = DefaultComparer;
            }
            for (int i = 0; i != count; i++)
            {
                T element = ExtractAt(index + i);
                int toIndex = BinarySearch(index, i, element, comparer);
                if (toIndex < 0)
                {
                    toIndex = ~toIndex;
                }
                Insert(toIndex, element);
            }
        }
    }

    /// <summary>Copies the elements of the vector to a new array.</summary>
    public T[] ToArray()
    {
        T[] array = new T[Count];
        int index = 0;
        foreach (T element in this)
        {
            array[index] = element;
            index++;
        }
        return array;
    }

    /// <summary>Determines whether every element in the vector matches the conditions defined by the predicate.</summary>
    /// <exception cref="ArgumentNullException">If the match predicate is null.</exception>
    /// <param name="match">I: The predicate delegate that defines the conditions to check against the elements.</param>
    public bool TrueForAll(Predicate<T> match)
    {
        CheckMatchPredicate(match);
        bool trueForAll = true;
        foreach (T element in this)
        {
            if (!match(element))
            {
                trueForAll = false;
                break;
            }
        }
        return trueForAll;
    }

    // Services in addition to the support in line with existing collections.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Returns the vector node at the specified index.</summary>
    /// <exception cref="ArgumentOutOfRangeException">
    ///     If the index is less than 0 or if the index is equal to or greater than the vector element count.
    /// </exception>
    /// <param name="index">I: Index, 0-based, must be valid.</param>
    public VectorNode<T> GetNode(int index)
    {
        CheckAtIndex(index);
        return _rootNode.GetNode(index, 0);
    }

    /// <summary>Returns a reference to the first node in vector order; this is the node containing element [0].</summary>
    /// <returns>Returns null if the vector is empty.</returns>
    public VectorNode<T> GetFirstNode()
    {
        VectorNode<T> node = _rootNode;
        while (node != null && node.Left != null)
        {
            node = node.Left;
        }
        return node;
    }

    /// <summary>Returns a reference to the last node in vector order; this is the node containing element [Count - 1].</summary>
    /// <returns>Returns null if the vector is empty.</returns>
    public VectorNode<T> GetLastNode()
    {
        VectorNode<T> node = _rootNode;
        while (node != null && node.Right != null)
        {
            node = node.Right;
        }
        return node;
    }

    /// <summary>Returns an enumerator for the vector.</summary>
    /// <remarks>
    ///     The enumerator is positioned just before the first element of the vector, such that a MoveNext is required
    ///     to step to the first element.
    /// </remarks>
    /// <returns>
    ///     Compared to <see cref="GetEnumerator"/> this method returns a typed enumerator rather than an enumerator
    ///     interface. This is useful in order to directly access the extra services such as a MovePrevious.
    /// </returns>
    public VectorEnumerator<T> GetVectorEnumerator()
    {
        return new VectorEnumerator<T>(this);
    }

    /// <summary>Returns an enumerator for the vector.</summary>
    /// <remarks>
    ///     The enumerator is positioned at the element with the specified index, and marked as fictive. A move is
    ///     required to clear the fictive indicator and to actually move to the element.
    /// </remarks>
    /// <param name="index">
    ///     I: Index of the element where to position. -1 can be used to position just before the first element, and the
    ///     vector element count can be used to position just beyond the last element.
    /// </param>
    public VectorEnumerator<T> GetVectorEnumerator(int index)
    {
        return new VectorEnumerator<T>(this, index);
    }

    /// <summary>Inserts an element in the vector at the specified index.</summary>
    /// <exception cref="ArgumentOutOfRangeException">If the index is less than 0 or if the index exceeds the vector element count.</exception>
    /// <param name="index">I: Index, zero based. Use the vector element count to insert at the end.</param>
    /// <param name="element">I: element to insert.</param>
    /// <returns>Returns a reference to the node that is created and inserted, and that contains the inserted element.</returns>
    public VectorNode<T> InsertAt(int index, T element)
    {
        CheckStartIndex(index);
        Int32 heightChange;
        _updateCount++;
        return VectorNode<T>.Insert(index, 0, element, null, ref _rootNode, out heightChange);
    }

    /// <summary>Extracts an element, removing it from the vector and returning it to the caller.</summary>
    /// <param name="index">I: Index of the element to extract, 0-based.</param>
    /// <returns>Returns the element removed from the vector.</returns>
    public T ExtractAt(int index)
    {
        CheckAtIndex(index);
        Int32 heightChange;
        _updateCount++;
        return VectorNode<T>.Delete(index, 0, null, ref _rootNode, out heightChange);
    }

    // Internal support for the vector enumerator class.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Update count, used to detect usage of the iterator after the vector has been modified.</summary>
    internal Int32 UpdateCount
    {
        [DebuggerStepThrough]
        get
        {
            return _updateCount;
        }
    }

    /// <summary>Root node, or null.</summary>
    internal VectorNode<T> RootNode
    {
        [DebuggerStepThrough]
        get
        {
            return _rootNode;
        }
    }

    /// <summary>Returns the height of the tree used for the vector.</summary>
    /// <returns>Returns 0 if the tree is empty, 1 if the tree contains a root node only, and so on.</returns>
    internal Int32 GetHeight()
    {
        return _rootNode == null? 0: _rootNode.GetHeight();
    }

    // Internal test and debug support.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Dumps the vector to the trace output, showing the tree structure of the vector.</summary>
    internal void Dump()
    {
        Trace.WriteLine(string.Format("Number of elements: {0}", Count));
        if (_rootNode == null)
        {
            Trace.WriteLine("Root null");
        }
        else
        {
            _rootNode.Dump(0);
        }
    }

    /// <summary>Establishes whether the vector is consistent and whether the vector tree is balanced.</summary>
    /// <remarks>This method is for white box test support.</remarks>
    internal bool GetConsistency()
    {
        Int32 height;
        int count;
        return _rootNode == null? true: _rootNode.GetConsistency(null, out height, out count);
    }
}

} // namespace
